Kernel matrices, as well as weighted graphs represented by them, are ubiquitous objects in machine learning, statistics and other related fields. The main drawback of using kernel methods (learning and inference using kernel matrices) is efficiency -- given $n$ input points, most kernel-based algorithms need to materialize the full $n \times n$ kernel matrix before performing any subsequent computation, thus incurring $\Omega(n^2)$ runtime. Breaking this quadratic barrier for various problems has therefore, been a subject of extensive research efforts. We break the quadratic barrier and obtain $\textit{subquadratic}$ time algorithms for several fundamental linear-algebraic and graph processing primitives, including approximating the top eigenvalue and eigenvector, spectral sparsification, solving linear systems, local clustering, low-rank approximation, arboricity estimation and counting weighted triangles. We build on the recent Kernel Density Estimation framework, which (after preprocessing in time subquadratic in $n$) can return estimates of row/column sums of the kernel matrix. In particular, we develop efficient reductions from $\textit{weighted vertex}$ and $\textit{weighted edge sampling}$ on kernel graphs, $\textit{simulating random walks}$ on kernel graphs, and $\textit{importance sampling}$ on matrices to Kernel Density Estimation and show that we can generate samples from these distributions in $\textit{sublinear}$ (in the support of the distribution) time. Our reductions are the central ingredient in each of our applications and we believe they may be of independent interest. We empirically demonstrate the efficacy of our algorithms on low-rank approximation (LRA) and spectral sparsification, where we observe a $\textbf{9x}$ decrease in the number of kernel evaluations over baselines for LRA and a $\textbf{41x}$ reduction in the graph size for spectral sparsification.

Recent work shows that the expressive power of Graph Neural Networks (GNNs) in distinguishing non-isomorphic graphs is exactly the same as that of the Weisfeiler-Lehman (WL) graph test. In particular, they show that the WL test can be simulated by GNNs. However, those simulations involve neural networks for the 'combine' function of size polynomial or even exponential in the number of graph nodes $n$, as well as feature vectors of length linear in $n$. We present an improved simulation of the WL test on GNNs with \emph{exponentially} lower complexity. In particular, the neural network implementing the combine function in each node has only a polylogarithmic number of parameters in $n$, and the feature vectors exchanged by the nodes of GNN consists of only $O(\log n)$ bits. We also give logarithmic lower bounds for the feature vector length and the size of the neural networks, showing the (near)-optimality of our construction.

数据驱动的算法可以通过从输入的训练样本中学习，可以使其内部结构或参数适应来自未知应用程序特定分布的输入。最近的一些作品将这种方法应用于数值线性代数中的问题，获得了绩效的显着经验增长。然而，尚无理论上的成功解释。在这项工作中，我们证明了这些算法的概括范围，在Gupta和Roughgarden提出的数据驱动算法选择的PAC学习框架内（Sicomp 2017）。我们的主要结果与Indyk等人的基于学习的低级近似算法的脂肪破碎维度紧密匹配（Neurips 2019）。我们的技术是一般的，并为数值线性代数中的许多其他最近提出的数据驱动算法提供了概括，涵盖了基于草图的基于草图的方法和基于多机的方法。这大大扩展了可用的PAC学习分析的数据驱动算法类别。

现实世界数据往往展现出长期分布，重量级别不平衡，其中大多数课程可以主导培训过程并改变少数阶层的决策边界。最近，研究人员调查了监督对长尾识别的对比学习的潜力，并证明它提供了强大的性能增益。在本文中，我们表明，虽然监督对比学习可以有助于提高性能，但过去的基线通过不平衡数据分布引入的均匀性差。这种差的均匀性在来自特征空间中具有差的少数阶级的样品中表现出来。为了解决这个问题，我们提出了有针对性的监督对比学习（TSC），从而提高了极度上的特征分布的均匀性。 TSC首先生成一组均匀分布在极度上的目标。然后，在训练期间使不同类别的特征会聚到这些不同的和均匀分布的目标。这迫使所有类别，包括少数群体类别，以维持特征空间中的统一分布，改善了类边界，即使在存在长尾数据的情况下也能提供更好的泛化。多个数据集的实验表明，TSC在长尾识别任务上实现了最先进的性能。

a *是图形搜索和路径查找的经典和流行方法。它假设存在启发式函数$ h（u，t）$，以估计从任何输入节点$ u $到目的$ t $的最短距离。传统上，通过域专家手工制度。然而，在过去的几年里，对学习启发式功能的兴趣日益增长。这种学习的启发式估计基于这些节点的“特征”的给定节点之间的距离。在本文中，我们正规化并启动了对这种特征的启发式的研究。特别地，我们考虑由常规嵌入和距离标记方案引起的启发式，并为用于表示每个曲线节点的尺寸或比特数以及A *算法的运行时间来提供下限。我们还表明，在自然的假设下，我们的下限几乎是最佳的。

对比学习是机器学习中最快的研究领域之一，因为它可以在没有标记数据的情况下学习有用的表示。然而，对比学学习易于特征抑制，即，它可能会丢弃与感兴趣的任务相关的重要信息，并学习无关的功能。过去的工作通过消除无关信息的手工制作的数据增强解决了这一限制。然而，这种方法不适用于所有数据集和任务。此外，当一个属性可以抑制与其他属性相关的特征时，数据增强在解决多属性分类中的功能抑制中失败。在本文中，我们分析了对比学习的目标函数，并正式证明它易于特征抑制。然后，我们提出预测对比学习（PCL），一种学习对特征抑制具有鲁棒的无监督表示的框架。关键的想法是强制学习的表示来预测输入，因此防止它丢弃重要信息。广泛的实验验证PCL是否强大地对特征抑制和优于各种数据集和任务的最先进的对比学习方法。

Audio DeepFakes are artificially generated utterances created using deep learning methods with the main aim to fool the listeners, most of such audio is highly convincing. Their quality is sufficient to pose a serious threat in terms of security and privacy, such as the reliability of news or defamation. To prevent the threats, multiple neural networks-based methods to detect generated speech have been proposed. In this work, we cover the topic of adversarial attacks, which decrease the performance of detectors by adding superficial (difficult to spot by a human) changes to input data. Our contribution contains evaluating the robustness of 3 detection architectures against adversarial attacks in two scenarios (white-box and using transferability mechanism) and enhancing it later by the use of adversarial training performed by our novel adaptive training method.

This short report reviews the current state of the research and methodology on theoretical and practical aspects of Artificial Neural Networks (ANN). It was prepared to gather state-of-the-art knowledge needed to construct complex, hypercomplex and fuzzy neural networks. The report reflects the individual interests of the authors and, by now means, cannot be treated as a comprehensive review of the ANN discipline. Considering the fast development of this field, it is currently impossible to do a detailed review of a considerable number of pages. The report is an outcome of the Project 'The Strategic Research Partnership for the mathematical aspects of complex, hypercomplex and fuzzy neural networks' meeting at the University of Warmia and Mazury in Olsztyn, Poland, organized in September 2022.

This paper presents the Crowd Score, a novel method to assess the funniness of jokes using large language models (LLMs) as AI judges. Our method relies on inducing different personalities into the LLM and aggregating the votes of the AI judges into a single score to rate jokes. We validate the votes using an auditing technique that checks if the explanation for a particular vote is reasonable using the LLM. We tested our methodology on 52 jokes in a crowd of four AI voters with different humour types: affiliative, self-enhancing, aggressive and self-defeating. Our results show that few-shot prompting leads to better results than zero-shot for the voting question. Personality induction showed that aggressive and self-defeating voters are significantly more inclined to find more jokes funny of a set of aggressive/self-defeating jokes than the affiliative and self-enhancing voters. The Crowd Score follows the same trend as human judges by assigning higher scores to jokes that are also considered funnier by human judges. We believe that our methodology could be applied to other creative domains such as story, poetry, slogans, etc. It could both help the adoption of a flexible and accurate standard approach to compare different work in the CC community under a common metric and by minimizing human participation in assessing creative artefacts, it could accelerate the prototyping of creative artefacts and reduce the cost of hiring human participants to rate creative artefacts.

Recently proposed systems for open-domain question answering (OpenQA) require large amounts of training data to achieve state-of-the-art performance. However, data annotation is known to be time-consuming and therefore expensive to acquire. As a result, the appropriate datasets are available only for a handful of languages (mainly English and Chinese). In this work, we introduce and publicly release PolQA, the first Polish dataset for OpenQA. It consists of 7,000 questions, 87,525 manually labeled evidence passages, and a corpus of over 7,097,322 candidate passages. Each question is classified according to its formulation, type, as well as entity type of the answer. This resource allows us to evaluate the impact of different annotation choices on the performance of the QA system and propose an efficient annotation strategy that increases the passage retrieval performance by 10.55 p.p. while reducing the annotation cost by 82%.